package com.demo.datastructure.tree;

import javax.swing.tree.TreeNode;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @description: letcode 55 平衡二叉树
 * @author: ljr
 * @time: 2021/6/7 15:33
 */
public class BalanceSearchTree {

    public boolean isBalanced(TreeNode root) {
        if(root == null){ return true; }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int level = 0;
        int drawLevel = 0;
        int num = 1;
        while(!deque.isEmpty()){
            int n = deque.size();
            for(int i = 0; i < n; i++){
                TreeNode node = deque.pop();
                if(node.left != null)deque.add(node.left);
                if(node.right != null)deque.add(node.right);
            }
            num = num*2;
            level++;
            if(num != deque.size() && drawLevel == 0){
                drawLevel = level;
            }

            if(level - drawLevel > 1){
                return false;
            }

        }
        return drawLevel == level || drawLevel+1 == level;
    }


    public boolean isBalanced2(TreeNode root) {
        if (root == null) {
            return true;
        }
        List<Integer> nums = new LinkedList<>();
        floor(root,nums);
        for(Integer num : nums){
            if(num > 1){
                return false;
            }
        }
        return true;
    }


    public boolean isBalanced3(TreeNode root) {
        return floor2(root) != -1;
    }

    private int floor(TreeNode node, List<Integer> nums){
        if(node == null){ return  0; }
        int leftNum = floor(node.left,nums);
        int rightNum = floor(node.right,nums);
        int num = Math.abs(leftNum - rightNum);
        nums.add(num);
        return Math.max(leftNum, rightNum)+1;
    }

    private int floor2(TreeNode node){
        if(node == null){ return  0; }
        int leftNum = floor2(node.left);
        if(leftNum == -1){ return -1;}
        int rightNum = floor2(node.right);
        if(rightNum == -1){ return -1;}
        return  Math.abs(leftNum - rightNum) > 1 ? -1 : Math.max(leftNum, rightNum)+1;
       /* int num = Math.abs(leftNum - rightNum);
        if(num > 1){
            return -1;
        }
        return Math.max(leftNum, rightNum)+1;*/
    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
   }
}
